package com.排序.练习题;

import java.util.concurrent.ThreadLocalRandom;

public class Leetcode912 {
    /**
     * 排序数组
     * 给你一个整数数组 nums，请你将该数组升序排列。
     *你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。
     *
     * 示例 1：
     * 输入：nums = [5,2,3,1]
     * 输出：[1,2,3,5]
     * 解释：数组排序后，某些数字的位置没有改变（例如，2 和 3），
     * 而其他数字的位置发生了改变（例如，1 和 5）。
     */
    public int[] sortArray(int[] nums) {
        quick(nums,0,nums.length-1);
        return nums;
    }

    private static void quick(int[] a, int left, int right) {
        if(left >= right){
            return;
        }
        int p = partition(a,left,right);
        quick(a,left,p-1);
        quick(a,p+1,right);
    }

    private static int partition(int[] a, int left, int right) {
        int idx = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
        swap(a, left, idx);
        int pv = a[left];
        int i = left + 1;
        int j = right;
        while (i <= j) {
            // i 从左向右找大的或者相等的
            while (i <= j && a[i] < pv) {
                i++;
            }
            // j 从右向左找小的或者相等的
            while (i <= j && a[j] > pv) {
                j--;
            }
            if (i <= j) {
                swap(a, i, j);
                i++;
                j--;
            }
        }
        swap(a, j, left);
        return j;
    }

    private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

}
